package com.study.homework;

import java.util.*;

/**
 * 关于栈、队列和递归的几个必知必会的代码实现
 * 栈
 * 用数组实现一个顺序栈
 * 用链表实现一个链式栈
 * 编程模拟实现一个浏览器的前进、后退功能
 * 队列
 * 用数组实现一个顺序队列
 * 用链表实现一个链式队列
 * 实现一个循环队列
 * 递归
 * 编程实现斐波那契数列求值 f(n)=f(n-1)+f(n-2)编程
 * 实现求阶乘 n!
 * 编程实现一组数据集合的全排列
 * 对应的 LeetCode 练习题（@Smallfly 整理）
 * 栈
 * Valid Parentheses（有效的括号）
 * 中文版：https://leetcode-cn.com/problems/valid-parentheses/
 * Longest Valid Parentheses（最长有效的括号）
 * 中文版：https://leetcode-cn.com/problems/longest-valid-parentheses/
 * Evaluate Reverse Polish Notatio（逆波兰表达式求值）
 * 中文版：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
 * 队列Design Circular Deque（设计一个双端队列）
 * 中文版：https://leetcode-cn.com/problems/design-circular-deque/
 * Sliding Window Maximum（滑动窗口最大值）
 * 中文版：https://leetcode-cn.com/problems/sliding-window-maximum/
 * 递归Climbing Stairs（爬楼梯）
 * 中文版：https://leetcode-cn.com/problems/climbing-stairs/
 */
public class Day2 {
    public static void main(String[] args) {
        // 用数组实现一个顺序栈
//        arrayStack();
        // 用链表实现一个链式栈
//        linkedStack();
        // 编程模拟实现一个浏览器的前进、后退功能
//        browser();
        // 用数组实现一个顺序队列
//        arrayQueue();
        // 用链表实现一个链式队列
//        linkedQueue();
        // 实现一个循环队列
//        arrayQueue();
        // 编程实现斐波那契数列求值 f(n)=f(n-1)+f(n-2)编程
//        for (int i = 1; i < 10; i++) {
//            System.out.println(fib(i));
//        }
        // 实现求阶乘 n!编程实现一组数据集合的全排列
//        System.out.println(factorial(10));
//        System.out.println(factorial1(10));
        // 编程实现一组数据集合的全排列
//        arrange();

        // Valid Parentheses（有效的括号）
//        System.out.println(isValid("()"));

        // Longest Valid Parentheses（最长有效的括号）
        // (())()(
//        String s = "()(()";
//        System.out.println(longestValidParentheses(s));
//        System.out.println(longestValidParentheses2(s));
//        System.out.println(longestValidParentheses3(s));
//        System.out.println(longestValidParentheses4(s));


        //最小权值 动态规划 习题 https://time.geekbang.org/column/article/74788
//        int[][] matrix = {{5}, {7, 8}, {2, 3, 4}, {4, 9, 6, 1}, {2, 7, 9, 4, 5}};
//        int path = shortestPath(matrix);
//        System.out.println(path);

        // 硬币 选择 动态规划
//        int[] coins = {1, 2, 4, 8};
//        System.out.println(minCoins(coins, 15));


        // Evaluate Reverse Polish Notatio（逆波兰表达式求值）
        // ["4","13","5","/","+"]
//        System.out.println(evalRPN(new String[]{"4", "13", "5", "/", "+"}));
//        System.out.println(evalRPN2(new String[]{"4", "13", "5", "/", "+"}));

        // 队列Design Circular Deque（设计一个双端队列）
//        circularDeque();

        // Sliding Window Maximum（滑动窗口最大值）
//        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
//        System.out.println(Arrays.toString(maxSlidingWindow2(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));

        // 递归Climbing Stairs（爬楼梯）

        System.out.println(climbStairs(38));
        System.out.println(climbStairs2(38));
    }

    public static int climbStairs2(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        int[] result = new int[n + 1];
        result[1] = 1;
        result[2] = 2;

        for (int i = 3; i <= n; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n];
    }

    public static int climbStairs(int n) {
        HashMap<Integer, Integer> map = new HashMap<>();
        return climbStairs(n, map);
    }

    public static int climbStairs(int n, Map<Integer, Integer> cache) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        Integer s = cache.get(n);

        if (s == null) {
            s = climbStairs(n - 1, cache) + climbStairs(n - 2, cache);
        }
        cache.put(n, s);
        return s;
    }

    static ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
    static int[] sNums;


    /**
     * 维护一个双向链表, 用来保存 k范围内 较大数的有序数列,
     */
    public static void clean_deque(int i, int k) {
        // remove indexes of elements not from sliding window
        if (!deq.isEmpty() && deq.getFirst() == i - k)
            deq.removeFirst();

        // remove from deq indexes of all elements
        // which are smaller than current element sNums[i]
        while (!deq.isEmpty() && sNums[i] > sNums[deq.getLast()]) deq.removeLast();
    }

    public static int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];
        if (k == 1) return nums;

        // init deque and output
        sNums = nums;
        int max_idx = 0;
        for (int i = 0; i < k; i++) {
            clean_deque(i, k);
            deq.addLast(i);
            // compute max in sNums[:k]
            if (nums[i] > nums[max_idx]) max_idx = i;
        }
        int[] output = new int[n - k + 1];
        output[0] = nums[max_idx];

        // build output
        for (int i = k; i < n; i++) {
            clean_deque(i, k);
            deq.addLast(i);
            output[i - k + 1] = nums[deq.getFirst()];
        }
        return output;
    }


    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length <= 0) {
            return new int[0];
        }
        if (nums.length <= k) {
            int max = 0;
            for (int num : nums) {
                if (max < num) {
                    max = num;
                }
            }
            return new int[]{max};
        }

        int len = nums.length - k + 1;
        int[] maxValues = new int[len];

        for (int i = 0; i < len; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i + k; j++) {
                int num = nums[j];
                if (max < num) {
                    max = num;
                }
            }
            maxValues[i] = max;
        }
        return maxValues;
    }

    private static void circularDeque() {
        //["MyCircularDeque","insertFront","getRear","deleteFront",
        // [56],[91],[],[],
        // "getRear","insertFront","isEmpty",
        // [],[90],[],
        // "isFull","getFront","getRear","getRear",
        // [],[],[],[],
        //
        // "insertFront","isEmpty","insertLast","isEmpty","getFront","getRear","getRear","insertFront","deleteFront","insertFront","insertFront","getFront","insertLast","insertLast","getRear","getFront","getRear","insertFront","getFront","insertLast","insertFront","insertLast","insertFront","getRear","deleteLast","isFull","insertLast","getFront","getFront","insertLast","deleteLast","getRear","insertLast","getFront","deleteFront","getRear","getFront","getRear","insertLast","insertFront","insertFront","insertLast","insertFront","deleteFront","insertLast","getFront","deleteFront","isFull","insertLast","getFront","insertLast","deleteFront","getFront","getRear","insertLast","insertLast","isFull","deleteLast","getFront","getFront","deleteLast","getRear","isEmpty","getFront","deleteLast","insertFront","isFull","deleteLast","deleteFront","insertLast","insertFront","insertFront","insertFront","deleteLast","getRear","deleteLast","insertFront","getRear","getFront","insertLast","getRear","getFront","insertLast","getFront","insertLast","getRear","getRear","deleteLast","deleteFront","getFront","deleteFront"]
        //[
        // [52],[],[90],[],[],[],[],[54],[],[40],[56],[],[46],[96],[],[],[],[89],[],[3],[54],[53],[22],[],[],[],[70],[],[],[2],[],[],[79],[],[],[],[],[],[17],[72],[58],[92],[94],[],[4],[],[],[],[57],[],[75],[],[],[],[50],[83],[],[],[],[],[],[],[],[],[],[15],[],[],[],[60],[22],[60],[39],[],[],[],[43],[],[],[94],[],[],[28],[],[9],[],[],[],[],[],[]]

        //[null,true,91,true,-1,true,false,false,90,91,91,true


        MyCircularDeque deque = new MyCircularDeque(56);
        System.out.println(deque.insertLast(91));
        System.out.println(deque.getRear());
        System.out.println(deque.deleteFront());
        System.out.println(deque.getRear());
        System.out.println(deque.insertLast(90));
        System.out.println(deque.isEmpty());
        System.out.println(deque.isFull());
        System.out.println(deque.getFront());
        System.out.println(deque.getRear());
        System.out.println(deque.getRear());

//        System.out.println(deque.deleteLast());
//        System.out.println(deque.insertFront(3));
//        System.out.println(deque.deleteLast());
//        System.out.println(deque.insertLast(4));
//        System.out.println(deque.deleteFront());
//        System.out.println(deque.isFull());
//        System.out.println(deque.insertFront(4));

        // t t t t t t 4 f t 4
    }

    public static int evalRPN2(String[] tokens) {
        int[] result = new int[tokens.length];
        int p = -1;
        for (String token : tokens) {
            switch (token) {
                case "+":
                    result[p - 1] = result[p - 1] + result[p];
                    p--;
                    break;
                case "-":
                    result[p - 1] = result[p - 1] - result[p];
                    p--;
                    break;
                case "*":
                    result[p - 1] = result[p - 1] * result[p];
                    p--;
                    break;
                case "/":
                    result[p - 1] = result[p - 1] / result[p];
                    p--;
                    break;
                default:
                    result[++p] = Integer.parseInt(token);
                    break;
            }
        }
        return result[p];
    }

    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    stack.push(-stack.pop() + stack.pop());
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int a = stack.pop();
                    stack.push(stack.pop() / a);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
                    break;
            }
        }
        return stack.pop();
    }


    private static int longestValidParentheses4(String s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right >= left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left >= right) {
                left = right = 0;
            }
        }
        return maxlength;

    }

    private static int longestValidParentheses3(String s) {
        Stack<Integer> stack = new Stack<>();
        char[] chars = s.toCharArray();

        int max = 0;

        int start = 0;
        while (chars[start] == ')') {
            start++;
        }
        stack.push(start - 1);
        for (int i = start; i < chars.length; i++) {
            char c = chars[i];
            if (c == '(') {
                stack.push(i);
            } else {
                // (()))((((())
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    int len = i - stack.peek();
                    max = max > len ? max : len;
                }
            }
        }
        return max;
    }

    private static int longestValidParentheses2(String s) {
        int[] ints = new int[s.length()];
        char[] chars = s.toCharArray();

        int max = 0;
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == '(') {
                continue;
            }
            if (chars[i - 1] == '(') {
                int record = i >= 2 ? ints[i - 2] : 0;
                ints[i] = record + 2;
            } else {
                if (i > ints[i - 1]) {
                    if (chars[i - ints[i - 1] - 1] == '(') {
                        int record = i - ints[i - 1] >= 2 ? ints[i - ints[i - 1] - 2] : 0;
                        ints[i] = ints[i - 1] + record + 2;
                    }
                }
            }
            max = ints[i] > max ? ints[i] : max;
        }
        return max;
    }

    private static int minCoins(int[] coins, int money) {
        for (int coin : coins) {
            if (money == coin) return 1;
        }

        boolean[][] cache = new boolean[money][money + 1];

        for (int coin : coins) {
            cache[0][coin] = true;
        }

        for (int i = 1; i < money; i++) {

            for (int j = 0; j <= money; j++) {

                if (cache[i - 1][j]) {
                    for (int coin : coins) {
                        int cash = j + coin;
                        if (cash <= money) {
                            cache[i][cash] = true;
                        }
                    }

                }
                if (cache[i][money]) {
                    return i + 1;
                }
            }
        }
        return -1;
    }

    private static int shortestPath(int[][] matrix) {
        if (matrix == null) {
            return -1;
        }
        if (matrix.length == 1) {
            return matrix[0][0];
        }
        int[][] result = new int[matrix.length][matrix[matrix.length - 1].length];

        result[0][0] = matrix[0][0];

        for (int i = 1; i < matrix.length; i++) {
            int[] level = matrix[i];
            for (int j = 0; j < level.length; j++) {
                if (j == 0) {
                    result[i][j] = result[i - 1][j] + matrix[i][j];
                } else if (j == level.length - 1) {
                    result[i][j] = result[i - 1][j - 1] + matrix[i][j];
                } else {
//                    result[i][2 * j - 1] = result[i - 1][j - 1] + matrix[i][j];
//                    result[i][2 * j] = result[i - 1][j] + matrix[i][j];

                    //过滤掉不必要的条目
                    result[i][j] = Math.min(result[i - 1][j - 1], result[i - 1][j]) + matrix[i][j];
                }
            }
        }

        int[] bottomLevel = result[matrix.length - 1];
        for (int aBottomLevel : bottomLevel) {
            if (aBottomLevel > 0) return aBottomLevel;
        }
        return -1;
    }

    private static int longestValidParentheses(String s) {
        int max = 0;
        int len = 0;

        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            for (int j = i + 2; j <= chars.length; j++) {
                String sub = s.substring(i, j);
                if (isValid1(sub)) {
                    len = j - i;
                    if (len > max) {
                        max = len;
                    }
                }
            }
        }
        return max;
    }

    public static boolean isValid1(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                if (')' != c) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.size() == 0;
    }

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        HashMap<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {

                if (stack.size() <= 0) {
                    return false;
                }

                Character pop = stack.pop();

                if (map.get(pop) != c) {
                    return false;
                }
            }
        }
        return stack.size() == 0;
    }


    private static void arrange() {
        int[] a = {1, 3, 5/*, 7, 9*/};
        int[] b = {5, 3, 7, 9, 1};

        List<List<Integer>> list = permute1(a);

        System.out.println(list);
    }

    private static List<List<Integer>> permute1(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> array = new ArrayList<>();
        for (int i : nums) {
            array.add(i);
        }
        arrange1(array, 0, list);
        return list;
    }

    private static void arrange1(List<Integer> a, int level, List<List<Integer>> list) {
        if (level == a.size() - 1) {
            list.add(new ArrayList<>(a));
            return;
        }

        for (int i = level; i < a.size(); i++) {
            Collections.swap(a, level, i);
            arrange1(a, level + 1, list);
            Collections.swap(a, level, i);
        }
    }

    private static List<List<Integer>> permute(int[] a) {
        return arrange(a, 0);
    }

    private static List<List<Integer>> arrange(int[] a, int startIndex) {
        if (startIndex >= a.length - 1) {
            return Arrays.asList(Arrays.asList(a[startIndex]));
        }
        List<List<Integer>> result = new ArrayList<>();
        List<List<Integer>> arrange = arrange(a, startIndex + 1);

        int value = a[startIndex];

        for (int i = 0; i < arrange.size(); i++) {
            List<Integer> l = arrange.get(i);
            int len = l.size() + 1;
            for (int j = 0; j < len; j++) {
                List<Integer> temp = new ArrayList<>(l);
                temp.add(j, value);
                result.add(temp);
            }
        }

        return result;
    }

    private static long factorial1(int count) {
        int result = 1;

        while (count > 1) {
            result *= count--;
        }
        return result;
    }

    private static long factorial(int count) {
        if (count == 0) {
            return 1;
        }
        if (count == 1) {
            return 1;
        }
        return count * factorial(count - 1);
    }

    private static int fib(int index) {
        HashMap<Integer, Integer> map = new HashMap<>();
        return getFibonacci(index, map);
    }

    private static int getFibonacci(int i, HashMap<Integer, Integer> map) {
        if (i == 1) {
            return 1;
        }
        if (i == 2) {
            return 1;
        }
        Integer integer = map.get(i);
        return integer == null ? getFibonacci(i - 1, map) + getFibonacci(i - 2, map) : integer;
    }

    private static void linkedQueue() {
        // push 1, 2, 3, 4
        // pop *2
        // push 5, 6
        // pop *
        LinkedQueue queue = new LinkedQueue();
        for (int i = 0; i < 3; i++) {
            queue.push(i);
        }
        System.out.println(queue.pop());//0
        System.out.println(queue.pop());//1
        queue.push(3);
        System.out.println(queue.pop());//2
        System.out.println(queue.pop());//3
    }

    private static void arrayQueue() {
        // add 1,2,3
        // pop * 2
        // add 4
        // pop * 2

        ArrayQueue queue = new ArrayQueue(4);
        for (int i = 0; i < 3; i++) {
            queue.push(i);
        }
        System.out.println(queue.pop());//0
        System.out.println(queue.pop());//1
        queue.push(3);
        System.out.println(queue.pop());//2
        System.out.println(queue.pop());//3
    }

    private static void browser() {
        Browser browser = new Browser();
        System.out.println(browser.link(1));//1
        System.out.println(browser.link(2));//2
        System.out.println(browser.link(3));//3
        System.out.println(browser.back());//2
        System.out.println(browser.back());//1
        System.out.println(browser.forward());//2
        System.out.println(browser.link(4));//4
        System.out.println(browser.back());//2
        System.out.println(browser.back());//1
    }

    private static void linkedStack() {
        LinkedStack stack = new LinkedStack();
        for (int i = 0; i < 10; i++) {
            stack.push(i);
        }
        for (int i = 0; i < 10; i++) {
            System.out.println(stack.pop());
        }
    }

    private static void arrayStack() {
        ArrayStack stack = new ArrayStack(5);
        for (int i = 0; i < 5; i++) {
            stack.push(i);
        }
        for (int i = 0; i < 5; i++) {
            System.out.println(stack.pop());
        }
    }
}
